#include <iostream>

using namespace std;

/*
Question: Given a sorted linked list, remove the duplicated node.
for example, intput is 1->1->2->3->3->4, the output is 2->4

*/

typedef struct _Node{
	_Node * Next;
	int value;
}Node, *PNode;

Node *CreateList(int *Arr, int n)
{
	if(n==0)
		return NULL;
	Node *head = new Node();
	head->value = Arr[0];
	head->Next = NULL;

	Node* pre = head;
	for( int i=1; i<n; i++)
	{
		Node *tmp = new Node();
		tmp->Next = NULL;
		tmp->value = Arr[i];
		pre->Next = tmp;
		pre = tmp;
	}
	return head;
}

bool IsDup( Node * head )
{
	if( !head )
		return false;
	int headValue = head->value;
	if( head->Next == NULL ||
		head->Next->value != headValue )
	{
		return false;
	}
	return true;
}

Node *RemoveDup( Node *Head)
{
	if( !Head )
		return NULL;

	Node *newHead = NULL;
	Node *newPre = NULL;
	Node *pre = NULL;
	Node *cur = Head;

	while(cur)
	{
		if(IsDup(cur))
		{
			// cur starts with dup head value
			int dupValue = cur->value;
			while( cur && cur->value == dupValue )
			{
				Node *tmp = cur;
				cur = cur->Next;
				delete tmp;
			}
		}
		else
		{
			if( !newHead )
			{
				newPre = newHead = cur;
				cur = cur->Next;
			}
			else
			{
				newPre->Next = cur;
				newPre = cur;
				cur = cur->Next;
			}
		}
	}

	if( newPre )
	{
		newPre->Next = NULL;
	}

	return newHead;
}

void DeleteList( Node *Head)
{
	if(!Head)
		return;
	while(Head)
	{
		Node *tmp = Head;
		Head = Head->Next;
		delete tmp;
	}
}

void PrintList( Node *Head )
{
	if( !Head )
	{
		return;
	}
	while( Head )
	{
		cout<<Head->value<<" ";
		Head = Head->Next;
	}
	cout<<endl;
	return;
}

int main(void)
{
	int arr[] = {1,1,2,3,3,4,5,6};
	Node * head = CreateList( arr, sizeof(arr)/sizeof(int));
	if(!head )
		cout<<"Fail to create list"<<endl;
	else
	{
		PrintList(head);
		head = RemoveDup(head);
		PrintList(head);
	}

	DeleteList(head);

	cout<<"Press any key to continue..."<<endl;
	return getchar();
}